package com.dmall.chapter07.section04;

import java.util.*;

public class WaterPuzzle {

    private int dest = -1;
    int[] dis = new int[54];

    public WaterPuzzle() {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[54];
        queue.add(0);
        visited[0] = true;
        dis[0] = 0;
        while (!queue.isEmpty()) {
            int cur = queue.remove();
            int a = cur / 10, b = cur % 10;
            // max ten = 5, max one = 3
            List<Integer> nexts = new ArrayList<>();
            //
            nexts.add(5 * 10 + b);
            nexts.add(a * 10 + 3);
            nexts.add(b);
            nexts.add(a * 10);
            // a桶给b桶
            int x = Math.min(a, 3 - b);
            nexts.add((a - x) * 10 + (b + x));
            // b桶给a桶
            int y = Math.min(5 - a, b);
            nexts.add((a + y) * 10 + (b - y));

            for (int next : nexts) {
                if (!visited[next]) {
                    queue.add(next);
                    visited[next] = true;
                    dis[next] = cur;
                    if (next / 10 == 4 || next % 10 == 4) {
                        dest = next;
                        return;
                    }
                }
            }
        }
    }

    public Iterable<Integer> result() {
        if (dest == -1) {
            return new ArrayList<>();
        }
        int cur = dest;
        List<Integer> list = new ArrayList<>();
        while (cur != 0) {
            list.add(cur);
            cur = dis[cur];
        }
        list.add(0);
        Collections.reverse(list);
        return list;
    }

    public Iterable<String> resultStr() {
        if (dest == -1) {
            return new ArrayList<>();
        }
        int cur = dest;
        List<String> list = new ArrayList<>();
        while (cur != 0) {
            list.add(cur / 10 + "," + cur % 10);
            cur = dis[cur];
        }
        list.add("0,0");
        Collections.reverse(list);
        return list;
    }

    public static void main(String[] args) {
        WaterPuzzle waterPuzzle = new WaterPuzzle();
        System.out.println(waterPuzzle.resultStr());
    }
}
